#include "StdAfx.h"
#include "Permutation.h"
#include "Permutations.h"
#include <string>
#include <algorithm>
#include <iostream>
#include <sstream>

using namespace std;

Permutations::Permutations(unsigned long *originalPermutation,int wordLen = 1, int groupSize = 1, int maxIntersectionForSave = 1, int minChainLengthForSave = 1, int maxChains=1)
: m_WordLen(wordLen), m_OriginalGroupSize(groupSize), m_MaxIntersectionForSave(maxIntersectionForSave), m_MinChainLengthForSave(minChainLengthForSave), m_MaxChains(maxChains)
{
	Permutation *perm = new Permutation(originalPermutation,wordLen,groupSize,1);
	m_Permutations.insert(m_Permutations.begin(),*perm);

	// Initialize XML
	m_Xml.SetDoc(XML_DECLARATION);
	m_Xml.AddElem(MULTIPLE_CHAINS_XML);
	m_Xml.AddAttrib(MULTIPLE_CHAINS_NAMESPACE_ATTR_XML, MULTIPLE_CHAINS_NAMESPACE_XML);
	m_Xml.AddAttrib(MULTIPLE_CHAINS_NAMSPACE_XSI_ATTR_XML, MULTIPLE_CHAINS_NAMESPACE_XSI_XML);
	m_Xml.AddAttrib(MULTIPLE_CHAINS_SCHEMA_ATTR_XML,MULTIPLE_CHAINS_SCHEMA_XML);	
}

Permutations::~Permutations(void)
{ }

int Permutations::GetGroupSize() const
{
	return m_OriginalGroupSize;
}
void Permutations::InsertPerm(const Permutation &perm)
{
	m_Permutations.push_back(perm);
}

Permutation *Permutations::GetOriginalPermutation()
{
	if (m_Permutations.empty())
	{
		return NULL;
	}
	else 
	{	
		return &(m_Permutations[0]);
	}
}

// This functions creates all the permutations and links between them
// The algorithm links a permutation to all permutations created before it with small intersections
// To go over all permutations and find chains we have to start from the 1st one and go over the list
void Permutations::Fill()
{
	if (m_Permutations.empty())
	{	
		return;
	}

	Permutation *perm = GetOriginalPermutation();
	Permutation *nextPerm = perm->NextPermutation();
	int currentPermName = 2; // 1st perm is 1
	
	while (nextPerm != NULL) // NULL - last permutation
	{
		perm = nextPerm;
		nextPerm = perm->NextPermutation();
		
		// Check if we want to save this permutation
		int intersectionWithOriginal = perm->CountIntersection(GetOriginalPermutation()->GetMatrixRows(),m_OriginalGroupSize);
		if (intersectionWithOriginal<=m_MaxIntersectionForSave)
		{
			AddPermutationToList(perm,intersectionWithOriginal);
		}
	}
}

//--------------------------------------------------------------------------
// CreateAllChains - creates all chains, writes to XML (does not output)
//--------------------------------------------------------------------------
void Permutations::CreateAllChains()
{
	Chain tempChain(m_MaxIntersectionForSave);
	Permutation* perm = GetOriginalPermutation(); 
	tempChain.PushPermutation(perm);
	m_Chains.clear();
	CreateChains(perm,tempChain,0);
	m_Chains.clear();
}

//--------------------------------------------------------------------------
// CreateChains: recursive function for creating chains
// Parameters: 
// perm - current permutation to work with
// chain - current chain
// chaincount - chain index for chain name (how many chains were saved)
// returns: updated chain count
//--------------------------------------------------------------------------
int Permutations::CreateChains(Permutation *perm, Chain chain, int chainCount)
{
	vector<RelatedPermutation>::iterator it = perm->GetRelatedPermsBegin();
	stringstream chainName;
	// Try to add all related perms
	for (; it< perm->GetRelatedPermsEnd(); it++)
	{
		// Group index is 1 based, vector is 0 based
		Permutation *newPerm = &m_Permutations[it->GetIndex()-1];
		if (chain.IsLegalToAdd(newPerm))
		{
			// Add new matrix to chain
			chain.PushPermutation(newPerm);
			chainCount = CreateChains(newPerm,chain,chainCount);
			// Remove new matrix from chain - all options with it were checked recursively
			chain.PopPermutation();
		}
		// Stop trying if we have enough chains
		if (chainCount >= m_MaxChains)
		{
			return chainCount;
		}
	}
	// Only save if this chain is long enough
	if (chain.GetLength() >= m_MinChainLengthForSave)
	{
		Chain *copyForSave = chain.Clone();
		copyForSave->RemoveIntersections();

		// Recheck that chain is long enough
		if (chain.GetLength() >= m_MinChainLengthForSave)
		{
			// Check if chain already exists
			bool found = false;
			for (vector<Chain>::iterator it = m_Chains.begin(); it < m_Chains.end() && !found; it++)
			{
				if ((*it)==*copyForSave)
				{
					found = true;
				}
			}

			if (!found)
			{
				chainCount++;
				chainName.flush();
				chainName << "chain" << chainCount;
				copyForSave->SetName(chainName.str());
				// Save chain to XML and chain list
				copyForSave->Save(m_Xml);
				m_Chains.push_back(*copyForSave);
			}
		}		
	}
	return chainCount;
}

//--------------------------------------------------------------------------
// SaveToFile: Saves XML to a file
// Parameters:
// filename - output file name
//--------------------------------------------------------------------------
void Permutations::SaveToFile(string filename) 
{
	m_Xml.Save(filename);
}

//--------------------------------------------------------------------------
/// AddPermutationTolist: Gets a permutation, checks if it is a new one 
//  if so, adds it to list
/// Assumes permutation is OK to add to original group, removes intersection with original group
//--------------------------------------------------------------------------
void Permutations::AddPermutationToList(Permutation *perm,int intersectionWithOriginal)
{
	Permutation *originalPerm  = GetOriginalPermutation(); // update pointers
	int currentPermName = m_Permutations.size()+1; // Names are 1 based

	// Set group name
	perm->SetName(currentPermName);
	
	vector<int> permutationsToLinkTo;
	permutationsToLinkTo.push_back(1); // Add original group or this function wouldn't be called

	// Remove intersection with original from permutation
	unsigned long *permWithoutIntersectionWithOriginal = Permutation::GetMatrixWithoutIntersection(perm->GetMatrixRows(), 
																perm->GetGroupSize(), originalPerm->GetMatrixRows(), 
																originalPerm->GetGroupSize(),
																intersectionWithOriginal);

	// If we got NULL, the whole group was removed, so it is useless
	if (NULL==permWithoutIntersectionWithOriginal)
	{
		return;
	}
	perm->UpdateMatrix(permWithoutIntersectionWithOriginal,perm->GetGroupSize() - intersectionWithOriginal);

	// Go over all permutations we already saved and list this one as related to them
	vector<Permutation>::iterator it = m_Permutations.begin();
	// 1st matrix is original one and we dealt with it
	it++;
	bool isDuplicatePermutation = false;
	while (it != m_Permutations.end() && !isDuplicatePermutation)
	{
		int intersectionWithCurrentMatrix = perm->CountIntersection(it->GetMatrixRows(),it->GetGroupSize());
		// Check if this is the same permutation - if their sizes match and the intersection is all the group
		// If one is bigger the chains they create will be different and we need both.
		if (perm->GetGroupSize() == it->GetGroupSize() && intersectionWithCurrentMatrix == perm->GetGroupSize()) 
		{
			isDuplicatePermutation = true;
		}
		else 
		{
			// If the intersection is small but this matrix is not contained in the other (or vice versa), link them
			if (intersectionWithCurrentMatrix <= m_MaxIntersectionForSave && intersectionWithCurrentMatrix != perm->GetGroupSize() && intersectionWithCurrentMatrix != it->GetGroupSize())
			{
					permutationsToLinkTo.push_back(it->GetName());
			}
		}
		it++;
	}
	
	// If this isn't a duplicate permutation, go over the list and add it to each permutation there
	// Then add it to list
	if (!isDuplicatePermutation)
	{
		vector<int>::iterator it = permutationsToLinkTo.begin();
		for (; it!=permutationsToLinkTo.end(); it++)
		{
			int permToAddToIndex = *it-1;
			int intersectionWithCurrentMatrix = perm->CountIntersection(m_Permutations[permToAddToIndex].GetMatrixRows(),m_Permutations[permToAddToIndex].GetGroupSize());

			// Add links to both permutations - this is important for recursive chain finding (the order of the chain matters)
			m_Permutations[permToAddToIndex].AddRelatedPerm(RelatedPermutation(perm->GetName(),intersectionWithCurrentMatrix));
			perm->AddRelatedPerm(RelatedPermutation(*it,intersectionWithCurrentMatrix));
		}

		//save
		m_Permutations.push_back(*perm);
	}		
}

//--------------------------------------------------------------------------
// SaveGroups - saves the permutations groups + related groups to xml
// For debugging
// parameters : 
// filename - output file name
//--------------------------------------------------------------------------
void Permutations::SaveGroups(string filename)
{
	CMarkup xmlFile;
	xmlFile.AddElem(GROUPS_XML_GROUPS);
	for (vector<Permutation>::iterator it = m_Permutations.begin(); it < m_Permutations.end(); it++)
	{
		it->SaveToXml(xmlFile);
		it->SaveRelatedPermsToXml(xmlFile);
	}
	xmlFile.OutOfElem();
	xmlFile.Save(filename);
}

//--------------------------------------------------------------------------
// CreatePermutationsObject - creates a permutations object from xml 
//                            parameters
// parameters : 
// xml - input xml
//--------------------------------------------------------------------------
Permutations *Permutations::CreatePermutationsObject(CMarkup &xmlFile)
{
	// Enter file
	xmlFile.FindElem();
	xmlFile.IntoElem();

	// Find general parameters part and get word length
	if (xmlFile.FindElem(INPUT_XML_GENERAL) == false)
	{
		cout << "Could not load general parameters " << endl;
		return NULL;
	}
	xmlFile.IntoElem();

	if (xmlFile.FindElem(INPUT_XML_N) == false)
	{
		cout << "Could not find parameter n (word length) " << endl;
		return NULL;
	}
	int wordLen = atoi((xmlFile.GetData()).c_str());
	xmlFile.OutOfElem();

	// Find permutations node and get the rest of the parameters	
	if (xmlFile.FindElem(INPUT_XML_PERMUTATIONS) == false)
	{
		cout << "Could not load permutation parameters" << endl;
		return NULL;
	}
	xmlFile.IntoElem();	
	if (xmlFile.FindElem(INPUT_XML_INITIAL_GROUP) == false)
	{
		cout << "Could not find initial group" << endl;
		return NULL;
	}
	xmlFile.IntoElem();
	vector<unsigned long> initialPermVector;
	int groupSize = 0;
	
	while (xmlFile.FindElem(VERTEX_XML))
	{
			//create the vector name
			string vertexNameStr;
			// Try this or next vertex
			if (xmlFile.GetData() == "")
			{
				xmlFile.FindElem(VERTEX_XML); // next vertex
			}
			groupSize++;
			vertexNameStr = xmlFile.GetData();
			int size = vertexNameStr.size();
			
			int vertex = 0;
			for(int i=0; i< size; i++)
			{
				int temp = (vertexNameStr.c_str()[i]=='1') ? 1 : 0;
				vertex = vertex*2 + temp;
			}

			initialPermVector.push_back(vertex);						
	}

	xmlFile.OutOfElem();
	if (initialPermVector.size() == 0)
	{
		cout << "Initial group is empty " << endl;
		return NULL;
	}

	if (xmlFile.FindElem(INPUT_XML_MIN_CHAIN_LEN) == false)
	{
		cout << "Could not load minimum chain length for save" << endl;
		return NULL;
	}
	int minChainLenForSave = atoi((xmlFile.GetData()).c_str());

	if (xmlFile.FindElem(INPUT_XML_MAX_INTERSECTION_SIZE) == false)
	{
		cout << "Could not load maximal intersection between 2 groups " << endl;
		return NULL;
	}
	int maxIntersectionSize = atoi((xmlFile.GetData()).c_str());

	if (xmlFile.FindElem(INPUT_XML_MAX_CHAINS) == false)
	{
		cout << "Could not load maximum number of chains" << endl;
		return NULL;
	}
	int maxChains = atoi((xmlFile.GetData()).c_str());
	
	// copy to pointer
	unsigned long *initialPerm = new unsigned long[groupSize];
	int i=0;
	for (vector<unsigned long>::iterator it = initialPermVector.begin(); it < initialPermVector.end(); it++)
	{
		initialPerm[i] = (*it);
		i++;
	}
	Permutations *permutations = new Permutations(initialPerm,wordLen,groupSize,maxIntersectionSize,minChainLenForSave,maxChains);

	return permutations;
}

//--------------------------------------------------------------------------
// Run - fills permutations object and creates all chains
// Parameters:
// outputFileName - file name for output
//--------------------------------------------------------------------------
void Permutations::Run(string outputFileName)
{
	Fill();
	CreateAllChains();
	SaveToFile(outputFileName);
}